package com.msa.sort;

import java.util.Comparator;

/**
 * 排序算法<a href="https://jingyan.baidu.com/article/db55b609f856604ba30a2f18.html">八大排序算法</a>
 *
 * @author 毕子航 951755883@qq.com
 * @date 2018/12/21
 */
public class SortKit {
	/**
	 * 冒泡排序
	 *
	 * @param args
	 * @return
	 */
	public static <T> T[] bubbleSort(T[] args, Comparator<T> comparator) {
		T exchangeStorage;
		for (int i = 0; i < args.length; i++) {
			//exchange
			for (int j = i + 1; j < args.length; j++) {
				if (comparator.compare(args[i], args[j]) > 0) {
					exchangeStorage = args[i];
					args[i] = args[j];
					args[j] = exchangeStorage;
				}
			}
		}
		return args;
	}

	/**
	 * 选择排序法
	 *
	 * @param args
	 * @return
	 */
	public static <T> T[] selectSort(T[] args, Comparator<T> comparator) {
		T exchangeStorage;
		for (int i = 0; i < args.length - 1; i++) {
			//从剩余的元素中依次找出最小的放在第0、1、2。。。位置上
			for (int j = i; j < args.length; j++) {
				if (comparator.compare(args[j], args[i]) > 0) {
					exchangeStorage = args[i];
					args[i] = args[j];
					args[j] = exchangeStorage;
				}
			}
		}
		return args;
	}

	/**
	 * 插入排序:
	 * 将待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
	 * 如果大于最大的，则不动；否则，一个一个往前挪直到到第一个
	 *
	 * @param args
	 * @return
	 */
	public static <T> T[] insertSortByFor(T[] args, Comparator<T> comparator) {
		if (args.length <= 1) {
			return args;
		}
		for (int i = 1; i < args.length; i++) {
			if (comparator.compare(args[i - 1], args[i]) > 0) {
				T exchangeStorage = args[i];
				for (int j = i - 1; j >= 0; j--) {
					//1.(序列值 > exchangeStorage && j == 0):后移并插入
					//2.(序列值 > exchangeStorage && j>0),移动
					//3.否则 (序列值 < exchangeStorage):插入;
					if (comparator.compare(args[j], exchangeStorage) > 0) {
						//移动
						args[j + 1] = args[j];
						//移动结束，插入
						if (j == 0) {
							args[j] = exchangeStorage;
							break;
						}
					} else {
						//插入
						args[j + 1] = exchangeStorage;
						break;
					}
				}
			}
		}
		return args;
	}

	/**
	 * 插入排序
	 *
	 * @param args
	 * @return
	 */
	public static <T> T[] insertSortByWhile(T[] args, Comparator<T> comparator) {
		if (args.length <= 1) {
			return args;
		}
		for (int i = 1; i < args.length; i++) {
			T exchangeStorage = args[i];
			int j = i;
			while (j > 0 && comparator.compare(args[j - 1], exchangeStorage) >= 0) {
				args[j] = args[j - 1];
				j--;
			}
			args[j] = exchangeStorage;
		}
		return args;
	}
}
